package 力扣日常刷题.木23一月.第01天301;

/**
 * @author 帅小伙
 * @date 2022/3/1
 * @description
 */
public class Demo04矩阵中的路径 {


    public boolean exist(char[][]board,String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(dfs(board,words,0,0,0));
            }
        }
        return false;
    }

    boolean dfs(char[][] board,char[] word,int i,int j,int k){
        if(i >= board.length || i <0 || j < 0 || j >= board[0].length || board[i][j]!=word[k])return false;
        if(k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board,word,i+1,j,k+1) ||
                dfs(board,word,i-1,j,k+1)||
                dfs(board,word,i,j+1,k+1)||
                dfs(board,word,i,j - 1,k+1);
        board[i][j] = word[k];
        return res;
    }

}
